home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Dr. Windows 3
/
dr win3.zip
/
dr win3
/
UTILITY1
/
ATT302.ZIP
/
QS.BAS
< prev
next >
Wrap
BASIC Source File
|
1993-08-28
|
3KB
|
95 lines
DefInt A-Z
'This code from the VBDOS sample sort application
'
' ============================== QuickSort ===================================
' QuickSort works by picking a random "pivot" element in SortArray, then
' moving every element that is bigger to one side of the pivot, and every
' element that is smaller to the other side. QuickSort is then called
' recursively with the two subdivisions created by the pivot. Once the
' number of elements in a subdivision reaches two, the recursive calls end
' and the array is sorted.
' ============================================================================
'
Sub QuickSort (Low, High)
If Low < High Then
' Only two elements in this subdivision; swap them if they are out of
' order, then end recursive calls:
If High - Low = 1 Then
If TaskList(Low).WTitle$ > TaskList(High).WTitle$ Then
T$ = TaskList(Low).WTitle
TH = TaskList(Low).HWnd
TaskList(Low).WTitle = TaskList(High).WTitle
TaskList(Low).HWnd = TaskList(High).HWnd
TaskList(High).WTitle = T$
TaskList(High).HWnd = TH
End If
Else
' Pick a pivot element at random, then move it to the end:
RandIndex = RandInt%(Low, High)
'SWAP TaskList$(High), TaskList$(RandIndex)
T$ = TaskList(RandIndex).WTitle
TH = TaskList(RandIndex).HWnd
TaskList(RandIndex).WTitle = TaskList(High).WTitle
TaskList(RandIndex).HWnd = TaskList(High).HWnd
TaskList(High).WTitle = T$
TaskList(High).HWnd = TH
mPartition$ = TaskList(High).WTitle
Do
' Move in from both sides towards the pivot element:
I = Low: J = High
Do While (I < J) And (TaskList(I).WTitle <= mPartition$)
I = I + 1
Loop
Do While (J > I) And (TaskList(J).WTitle >= mPartition$)
J = J - 1
Loop
' If we haven't reached the pivot element, it means that two
' elements on either side are out of order, so swap them:
If I < J Then
'SWAP TaskList$(I), TaskList$(J)
T$ = TaskList(I).WTitle
TH = TaskList(I).HWnd
TaskList(I).WTitle = TaskList(J).WTitle
TaskList(I).HWnd = TaskList(J).HWnd
TaskList(J).WTitle = T$
TaskList(J).HWnd = TH
End If
Loop While I < J
' Move the pivot element back to its proper place in the array:
'SWAP TaskList$(I), TaskList$(High)
T$ = TaskList(I).WTitle
TH = TaskList(I).HWnd
TaskList(I).WTitle = TaskList(High).WTitle
TaskList(I).HWnd = TaskList(High).HWnd
TaskList(High).WTitle = T$
TaskList(High).HWnd = TH
' Recursively call the QuickSort procedure (pass the smaller
' subdivision first to use less stack space):
If (I - Low) < (High - I) Then
QuickSort Low, I - 1
QuickSort I + 1, High
Else
QuickSort I + 1, High
QuickSort Low, I - 1
End If
End If
End If
End Sub
' =============================== RandInt% ===================================
' Returns a random integer greater than or equal to the Lower parameter
' and less than or equal to the Upper parameter.
' ============================================================================
'
Static Function RandInt% (lower, Upper)
RandInt% = Int(Rnd * (Upper - lower + 1)) + lower
End Function